package com.zhugang.week13.binarysearch;

/**
 * @program algorithms
 * @description: peakIndexInMountainArray
 * @author: chanzhugang
 * @create: 2022/11/25 20:38
 */
public class PeakIndexInMountainArray {

    /**
     * 852 山脉数组的峰顶索引
     * https://leetcode.cn/problems/peak-index-in-a-mountain-array/
     *
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        /**
         * 二分效率更好
         * 画个图， 上坡、峰顶、下坡
         */
        int n = arr.length;
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (mid == 0) {
                low = mid + 1;
            } else if (mid == n - 1) {
                high = mid - 1;
            } else if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if (arr[mid] > arr[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}